package offer.tree;

/**
 * @author DengYuan2
 * @create 2021-02-26 19:53
 */
public class n_26 {
    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(8);
        TreeNode t2 = new TreeNode(8);
        TreeNode t3 = new TreeNode(9);
        TreeNode t4 = new TreeNode(2);
        TreeNode t5 = new TreeNode(5);
        t1.left=t2;
        t2.left=t3;
        t3.left=t4;
        t3.right=t5;
        TreeNode s1 = new TreeNode(8);
        TreeNode s2 = new TreeNode(9);
        TreeNode s3 = new TreeNode(2);
        TreeNode s4 = new TreeNode(2);
        s1.left=s2;
        s2.left=s3;
//        s2.right=s4;
        n_26 n = new n_26();
        boolean res = n.HasSubtree(t1, s1);
        System.out.println(res);

    }

    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if ( root1==null ||root2==null){
            return false;
        }
        return helper(root1,root2)||HasSubtree(root1.left,root2)||HasSubtree(root1.right,root2);
    }

    public boolean helper(TreeNode root1,TreeNode root2){
        if (root2==null){
            return true;
        }
        if (root1==null){
            return false;
        }
        if (root1.val!=root2.val){
            return false;
        }
        return helper(root1.right,root2.right)&&helper(root1.left,root2.left);
    }

}

